\documentclass{beamer}
\usepackage[utf8]{inputenc}
\usepackage{vwcol}
\usepackage[T1]{fontenc} 
\usepackage{beamerthemeshadow}
\usepackage[ngerman]{babel}
\usepackage{hhline}
%\usepackage{default}
\usetheme{Berlin}
\usepackage{multicol} 
\usepackage{amsmath} 
\usepackage{graphicx} % support the \includegraphics command and options
\usepackage{booktabs} % for much better looking tables
\usepackage{array} % for better arrays (eg matrices) in maths
\usepackage{paralist} % very flexible & customisable lists (eg. enumerate/itemize, etc.)
\usepackage{verbatim} % adds environment for commenting out blocks of text & for better verbatim
\usepackage{amsmath}
\usepackage{verbatim} 
\usepackage{color}
\usepackage{amssymb}
\usepackage{tikz}
\usepackage{algorithm2e}
\newcommand*{\tabbox}[2][t]{%
    \vspace{0pt}\parbox[#1][3.7\baselineskip]{1cm}{\strut#2\strut}}
\addto\captionsngerman{
\renewcommand{\figurename}{Figure}
} 
\setbeamertemplate{caption}[numbered]
\addtobeamertemplate{navigation symbols}{}{%
    \usebeamerfont{footline}%
    \usebeamercolor[fg]{footline}%
    \hspace{1em}%
    \insertframenumber/\inserttotalframenumber
}

\usepackage{listings}

\lstset{language=Java,
                basicstyle=\footnotesize\ttfamily,
                keywordstyle=\footnotesize\color{blue}\ttfamily,
}

\begin{document}
\title{Authenticated Data Structures}  
\author{Lennart Leder, Sourav Saraf, Nicholas Addae, Tobias Hardes}
\institute[University of Paderborn]
{
  University of Paderborn \\
 Project group \grqq Authenticated Information Systems\grqq
}
\date{21.08.2014} 
\frame{\titlepage} 
\frame{
	\frametitle{Table of contents}
	\tableofcontents
}
\section{Introduction and motivation}
\begin{frame}{Scope}
	\begin{figure}[ht!]
	\centering
		\includegraphics[width=1.0\textwidth]{images/pg_whiteboard_from_friday_2507.jpg}
	\caption{Whiteboard}
	\label{fig:Whiteboard}
	\end{figure}
\end{frame}
\begin{frame}{Scope}
	\begin{itemize}
	 \item Used for:
	 \begin{itemize}
	  \item Generation of the proof
	  \item Check of consistency and integrity on the client
	 \end{itemize}
	  \item Must be consistent with the file systems
	  \item Forging the proof must be difficult
	  \item Different data structures can be used
	  \begin{itemize}
	   \item Merkle Hash Tree
	   \item Skip List
	   \item Various dictionaries
	   \item ...
	  \end{itemize}

	\end{itemize}

\end{frame}
\begin{frame}{Scenario}
	\begin{itemize}
	 \item User performs some operation
	 \begin{itemize}
	  \item Insert
	  \item Update
	  \item Delete
	  \item Search
	 \end{itemize}
	\item Server perfoms this operation
	\item Authenticated Data Structure 
	\begin{itemize}
	 \item Keeps information about the file system
	 \item Using this information, a proof is generated
	 \item Used for verification
	\end{itemize}
	\item Proof is used by the client to verify the operation
	\end{itemize}
\end{frame}
\section{Overview and Architecture}
\begin{frame}{Architecture}
\begin{itemize}
 \item Server complete untrusted
 \item Authentication service is the fokus
\end{itemize}
	\begin{figure}[ht]
	\centering
		\includegraphics[width=1.0\textwidth]{images/architecture.png}
	\caption{Architecture}
	\label{fig:Architecture}
	\end{figure}
	\end{frame}
\begin{frame}[fragile]{Scenario}
\begin{itemize}
 \item Simple hash map as a file system
\end{itemize}
\begin{lstlisting}
  private  Map<Number, Number> map = new HashMap();
  private void generateMap()
  {
  Random ran = new Random();
    for(int i =0; i< 10; i++)
    {
      this.map.put(i, ran.nextInt(max - min) + min);
    }
  }
\end{lstlisting}
\begin{itemize}
 \item Usage of random numbers 
\end{itemize}
\end{frame}
\begin{frame}{What was done (I)}
\begin{itemize}
 \item SkipList
 \begin{itemize}
  \item Insert
  \item Delete
  \item Search
  \item printList
  \item Calculating authentication data
  \item 80\% of Proofgeneration 
 \end{itemize}
 \item Merkle Hash Tree
 \begin{itemize}
  \item Insert
  \item Delete
  \item Search
  \item Generation and verification of proof
 \end{itemize}
\end{itemize}
\end{frame}
 
\begin{frame}{What was done (II)}
 \begin{itemize}
 \item Authenticated Dictionaries
 \begin{itemize}
 \item ...
 \end{itemize}
\end{itemize}

\end{frame}

\section{Skip Lists}
\begin{frame}{Skip Lists}{Overview}
  \begin{itemize}
  \item $\mathcal{O}$(1) storage required on the client.
  \begin{itemize}
    \item \textbf{State information} or \textbf{digest} \textit{s}
    \item \textit{s} is the result of a hash function or a \textbf{proof}
  \end{itemize}
    \item Client $\mathcal{C}$ needs \textit{s} and a proof $\pi$ to verify the integrity
    \item Proof $\pi$ is calculated by the \textbf{authentication service} located on the server
    \item The security only based on \textbf{cryptographic hash functions}
    \item Building block: Authenticated skip list
   \item Skip list, augmented with structural and balancing information
	 \begin{itemize}
	  \item Hash map for Introduction $\rightarrow$ $(key(v),f(v))$
	  \item Cryptographic information
	  \item Stored by the server $\mathcal{S}$ (Authentication module)
	  \item Important to proof the correctness and consistency
	 \end{itemize}
	 \end{itemize}
\end{frame}
\frame{\frametitle{Skip lists - search operation }
\begin{multicols}{2}
\begin{figure}[ht!]
  \includegraphics[scale=0.35]{images/start_search66_1.png}
  \caption{Example for a skip list with 5 levels, including the state information s}
\end{figure}
\newpage
\begin{figure}[ht!]
  \includegraphics[scale=0.35]{images/start_search66_2.png}
  \caption{Search for element 66 in the skip list}
\end{figure}
\end{multicols}
}

\frame{\frametitle{Skip lists - search operation }
\begin{multicols}{2}
\begin{figure}[ht!]
  \includegraphics[scale=0.40]{images/proof_search_1.png}
  \caption{Flow information for the hashing}
\end{figure}
\newpage
\begin{figure}[ht!]
  \includegraphics[scale=0.40]{images/proof_search_2.png}
  \caption{Proof that is returned to the client - Verification starts from the bottom node}
\end{figure}
\end{multicols}
}\begin{frame}{Skip List Hashing}
     \begin{figure}[ht!]
    \includegraphics[scale=0.3]{images/skip_list_hashing.png}
  \end{figure}
\end{frame}
\begin{frame}{Example}{Search 66}
     \begin{figure}[ht!]
    \includegraphics[scale=0.37]{images/search_66_presentation.png}
  \end{figure}
\end{frame}

\begin{frame}{Basic concepts}
 \begin{itemize}
  \item Skip list as the basic concepts
  \begin{itemize}
   \item Data structure for authentication
   \item Data structure for the proof
  \end{itemize}
  \item Verification of the proof returns a hash hashValue
  \item Client stores the digest
  \item Hashvalue and digest should be equal
  \item [$\rightarrow$] Otherwise: Server cheated
 \end{itemize}
\end{frame}

\begin{frame}{Things to do}
 \begin{itemize}
  \item User performs operation $\rightarrow$ Perform this operation on the skip list
  \begin{itemize}
   \item Insert
   \item Delete
   \item ...
  \end{itemize}
  \item If there was a change - Recalculate authentication data aka. Do the hashing again
  \item Generate a proof with the authentication data
  \item Return the proof to the client
 \end{itemize}
\end{frame}
%Interfaces----------------
\begin{frame}[fragile]{ISkipList}
\begin{lstlisting}
public interface ISkipList {
  SkipList search(int key);
	
  SkipList insert(int key);

  void printList();
	
  SkipList delete(int key);
}
\end{lstlisting}
\begin{itemize}
 \item The returnvalue is the proof for verification
\end{itemize}

\end{frame}

\begin{frame}[fragile]{ISkipListProof}
\begin{lstlisting}
public interface ISkipListProof {
  public byte[] verifyProof(SkipList proof); //Calculated digest is returned
  protected SkipList generateProof(SkipList input,
  int key);
}
\end{lstlisting}
\begin{itemize}
 \item The class for the verification of the proof.
 \item $verifyProof(SkipList proof)$ is public for the client
 \item $generateProof(SkipList input,  int key);$ is just used on the server
\end{itemize}

\end{frame}
	
	
\begin{frame}[fragile]{What is done in main()?}
\begin{lstlisting}
public static void main(String args[]) {
  for (int i = 0; i < map.size(); i++) {
    int key = Integer.parseInt(map.get(i).toString());
    L.insert(key);
    L.printList();
    L = SkipListAuthentication.calculateAuthentication(L);
    proof =proofGen.generateProof(L,
    Integer.parseInt(map.get(i).toString())); 
  }
}
\end{lstlisting}
\end{frame}

\begin{frame}{From Hashmap to file system}
 \begin{multicols}{2}
    \begin{itemize}
    \item \textbf{Entry:} (inode, d(v))
      %\item \textbf{key}: Key according to the i-node
    \item \textbf{name}: The name in $\mathcal{FS}$
    \item \textbf{hash(file)}: Hash of file 
    \item \textbf{key(parent)}: Key of parent node 
    \item \textbf{key(sibling)}: Key of successor node 
    \item \textbf{key(backsibling)}: Key of predecessor node
    \item \textbf{key(child)}: Key of first child node
    \end{itemize}
  \newpage
    \begin{figure}[ht!]
      \includegraphics[scale=0.7]{images/filesystem.png}
    \end{figure}
  \end{multicols}
\end{frame}

\begin{frame}[fragile]{From Hashmap to file system}
\begin{itemize}
 \item How to store information of the file system?
\end{itemize}
\begin{lstlisting}
public class DS_FileSystem {
  private String name, hashValue;
  private int key_parent;
  private int key_sibling;
  private int key_backsibling;
  private int key_child;
  ....
}
\end{lstlisting}
\begin{itemize}
 \item Store as a hashmap $<Inode,DS\_FileSystem>$
\end{itemize}
\end{frame}

\begin{frame}{The situation}
 \begin{itemize}
  \item Functionality of a skip list: \textcolor{green}{working}
  \begin{itemize}
   \item Insert
   \item Update
   \item Delete
  \end{itemize}
  \item Adjustments of the basic algorithms for authenticated skip lists: \textcolor{green}{working}
  \item Calculating authentication data: \textcolor{green}{working} - \textcolor{yellow}{more testing needed}
  \item Generation of the proof: \textcolor{yellow}{more testing needed}
 \end{itemize}
\end{frame}

\begin{frame}
  \begin{figure}[ht!]
    \includegraphics[scale=0.40]{images/live_demo.jpg}
  \end{figure}
\end{frame}

\begin{frame}{Performance}
 \begin{itemize}
  \item Insert of 10 entries (Integer)$\rightarrow$ 40 ms - 60 ms, but...
  \begin{itemize}
   \item Insert to skip list takes no time
   \item Recalculation of authentication data takes 4 ms - 6 ms
   \item Nested loops $\rightarrow$ Easy debugging and monitoring, but bad runtime
   \item Optimization shouldn't be a problem :-)
  \end{itemize}
 \end{itemize}

\end{frame}

\section{Merkle Tree}
\begin{frame}{Scope}
	\begin{itemize}
	 \item One point	
	\end{itemize}
\end{frame}
\begin{frame}
 
\begin{figure}[ht!]
  \includegraphics[scale=0.40]{images/live_demo.jpg}
\end{figure}

\end{frame}
\section{Authenticated dictionaries}
\begin{frame}{Scope}
	\begin{itemize}
	 \item One point	
	\end{itemize}
\end{frame}
\begin{frame}
\begin{figure}[ht!]
  \includegraphics[scale=0.40]{images/live_demo.jpg}
\end{figure}
\end{frame}

\end{document}